Network-on-Chip (NoC) is a model for communications within systems implemented on a single chip (e.g., a silicon chip). In a NoC system, multiple devices such as processor cores, memories, IO devices, and specialized logic blocks exchange data (e.g., data packets) using a network. A switched NoC is constructed from multiple point-to-point data links interconnected by switches, such that the data packets can be relayed from any source device to any destination device over several data links, by way of specific routing decisions at the switches.
When packets from two or more sources arrive at a switch, a scheduler embedded in the switch decides how the packets will be forwarded. Each packet source may require a certain Quality of Service (QoS), such as a minimum bandwidth, maximum latency, or maximum jitter, to properly send information (e.g., low latency is needed for IP telephony). To guarantee a certain QoS for each packet source, various scheduling algorithms based on timestamp or round-robin methods have been developed. They offer algorithmic complexities ranging from constant to linear, with varying delay bounds, jitter, and fairness.
Deficit round robin is an attractive scheduling algorithm because of its relatively low complexity, especially when compared with timestamp-based scheduling algorithms. However, deficit round robin can serve one packet source for a long time before it “switches” to another packet source. This results in high jitter since the delay between any two consecutive packets that are forwarded from one packet source may vary greatly, a consequence that is undesirable from a QoS perspective. Another scheme that generally provides lower jitter than deficit round robin is called smoothed round robin. Although relatively simple to implement in a high level programming language, this scheme relies on processing a matrix that stores the relative weights of the sources in its rows, and hence its hardware implementation is more difficult.
In order to achieve improved QoS on simple systems such as NoCs, a low-jitter scheduling algorithm must be designed that can be easily implemented in hardware.